#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    vector<string>res;
    vector<string>tmp;
    string str;
    //判断截取位置是否合法
    //左闭右闭区间
    bool isright(string& s, int left, int right)
    {
        if (left > right) return false;

        //0开头的数字不合法
        if (s[left] == '0' && left < right) return false;

        //判断数字是否在【0，255】
        int num = 0;
        for (int i = left; i <= right; i++)
        {
            if (s[i] < '0' || s[i]>'9') return false;
            num = num * 10 + (s[i] - '0');
            if (num > 255) return false;
        }
        return true;
    }
    void dfs(string& s, int curi, int size)
    {
        if (size == 3)
        {
            //已经拿了三段了 判断一下最后一段是否合法
            if (isright(s, curi, s.size() - 1))
            {
                str = s.substr(curi);
                tmp.push_back(str);
                string ans = tmp[0] + '.' + tmp[1] + '.' + tmp[2] + '.' + tmp[3];
                tmp.pop_back();
                res.push_back(ans);
            }
            return;
        }
        for (int i = curi; i < s.size(); i++)
        {
            if (isright(s, curi, i))
            {
                str = s.substr(curi, i - curi + 1);
                tmp.push_back(str);
                dfs(s, i + 1, size + 1);
                tmp.pop_back();
            }
            else
            {
                break;
            }
        }

    }
    vector<string> restoreIpAddresses(string s)
    {
        res.clear();
        tmp.clear();
        if (s.size() < 4 || s.size() > 12) return res;
        dfs(s, 0, 0);
        return res;
    }
};
int main()
{
    Solution A;
    string s("25525511135");
    A.restoreIpAddresses(s);
    return 0;

}